package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 1638. 统计只差一个字符的子串数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/19 17:25
 */
public class CountSubstrings1638 {

    public static void main(String[] args) {
        CountSubstrings1638 test = new CountSubstrings1638();

        // 6
//        String a = "aba";
//        String b = "baba";

        // 3
//        String a = "ab";
//        String b = "bb";

        // 0
//        String a = "a";
//        String b = "a";

        // 10
        String a = "abe";
        String b = "bbc";

        int i = test.countSubstrings(a, b);
        System.out.println(i);
    }

    public int countSubstrings(String s, String t) {
        int m = s.length();
        int n = t.length();
        int[][] arr = new int[m][n];
        char[] as = s.toCharArray();
        char[] bs = t.toCharArray();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (as[i] == bs[j]) {
                    arr[i][j] = i > 0 && j > 0 ? arr[i - 1][j - 1] + 1 : 1;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (as[i] == bs[j]) {
                    int v = arr[i][j];
                    if (i >= v && j >= v) {
                        sum++;
                        if (i - v > 0 && j - v > 0) {
                            sum += arr[i - v - 1][j - v - 1];
                        }
                    }
                } else {
                    sum++;
                    if (i > 0 && j > 0) {
                        sum += arr[i - 1][j - 1];
                    }
                }
            }
        }
        return sum;
    }

}
